﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace DNA
{
    class AntSystem
    {
        public class Ant
        {
            public class sortAnts : IComparer<Ant>
            {
                int IComparer<Ant>.Compare(Ant x, Ant y)
                {
                    double valX = x.PathValue;
                    double valY = y.PathValue;
                    if (valX > valY)
                        return -1;
                    if (valX < valY)
                        return 1;
                    if (x.SummaricCost < y.SummaricCost)
                        return -1;
                    if (x.SummaricCost > y.SummaricCost)
                        return 1;
                    return 0;
                }
            }

            public static IComparer<Ant> cmp = new sortAnts();

            public Ant(DnaGraph graph)
            {
                _graph = graph;
            }

            public List<DnaGraph.Arc> visitedArcs = new List<DnaGraph.Arc>();
            public List<DnaGraph.Node> visitedNodes = new List<DnaGraph.Node>();

            public int PathValue = 0;
            public int SummaricCost = 0;
            protected DnaGraph _graph;

             virtual public void Walk(DnaGraph.Node start)
            {
                PathValue = 0;
                SummaricCost = 0;

                visitedArcs.RemoveRange(0,visitedArcs.Count);
                visitedNodes.RemoveRange(0,visitedNodes.Count);

                visitedNodes.Add(start);
                DnaGraph.Arc nextArc = start.GetNext(visitedNodes);
                if (nextArc == null)
                    return;

                visitedArcs.Add(nextArc);

                SummaricCost += nextArc.Cost;
                if (!(SummaricCost <= _graph.TotalCost))
                {
                    SummaricCost -= nextArc.Cost;
                    return;
                }

                DnaGraph.Node nextNode;
                while (SummaricCost <= _graph.TotalCost)
                {
                    nextNode = _graph.Nodes[nextArc.NodeString];
                    visitedNodes.Add(nextNode);
                    nextArc = nextNode.GetNext(visitedNodes);

                    if (nextArc == null)
                        return;                    

                    visitedArcs.Add(nextArc);

                    SummaricCost += nextArc.Cost;
                }
                visitedArcs.RemoveAt(visitedArcs.Count - 1);
                visitedNodes.RemoveAt(visitedNodes.Count - 1);
                SummaricCost -= nextArc.Cost;
            }
            
            public void Eval()
            {
                PathValue = visitedNodes.Count;
            }

            protected Ant(DnaGraph graph, List<DnaGraph.Node> nodes, List<DnaGraph.Arc> arcs) : this(graph)
            {
                visitedNodes = new List<DnaGraph.Node>();
                foreach (var item in nodes)
                    visitedNodes.Add(item);

                visitedArcs = new List<DnaGraph.Arc>();
                foreach (var item in arcs)
                    visitedArcs.Add(item);
            }
            

            internal void LayFeromone()
            {
                double addFeromone = (double)_graph.TotalCost/(double)SummaricCost*10.0;
                foreach (var arc in visitedArcs)
                {
                    arc.Feromon += addFeromone;
                    arc.changedFlag = true;
                }
                foreach (var node in visitedNodes)
                    node.changedFlag = true;
            }

            internal Ant Copy()
            {
                Ant newAnt = new Ant(_graph, visitedNodes, visitedArcs);
                newAnt.PathValue = PathValue;
                newAnt.SummaricCost = SummaricCost;
                return newAnt;
            }
        }

        public class NegativeAnt : Ant
        {
            public NegativeAnt(DnaGraph graph) : base(graph)
            {
             //   _graph = graph;
            }

            new public class sortAnts : IComparer<Ant>
            {
                int IComparer<Ant>.Compare(Ant x, Ant y)
                {
                    double valX = x.SummaricCost;
                    double valY = y.SummaricCost;
                    if (valX > valY)
                        return -1;
                    if (valX < valY)
                        return 1;
                    return 0;
                }
            }

            new public static IComparer<Ant> cmp = new sortAnts();
            
            public override void Walk(DnaGraph.Node start)
            {
                PathValue = 0;
                SummaricCost = 0;

                visitedArcs.RemoveRange(0, visitedArcs.Count);
                visitedNodes.RemoveRange(0, visitedNodes.Count);

                visitedNodes.Add(start);
                DnaGraph.Arc nextArc = start.GetNext(visitedNodes);
                if (nextArc == null)
                     return;

                visitedArcs.Add(nextArc);

                SummaricCost += nextArc.Cost;
                /*if (!(SummaricCost <= _graph.TotalCost))        //
                {
                    SummaricCost -= nextArc.Cost;
                    return;
                }*/

                DnaGraph.Node nextNode;
                while (true)
                {
                    nextNode = _graph.Nodes[nextArc.NodeString];
                    visitedNodes.Add(nextNode);
                    nextArc = nextNode.GetNext(visitedNodes);
                    if (nextArc == null)
                        return;
                    visitedArcs.Add(nextArc);

                    SummaricCost += nextArc.Cost;

                    //dodane odcięcia gdy koszt za duży

                /*    int noErrors = _graph.TotalCost - _graph.Nodes.Count;

                     if (SummaricCost - visitedNodes.Count > noErrors)
                        return;*/
                }
                visitedArcs.RemoveAt(visitedArcs.Count - 1);
                visitedNodes.RemoveAt(visitedNodes.Count - 1);
                SummaricCost -= nextArc.Cost;
            }
        }

        public class PositiveAnt : Ant
        {
            public PositiveAnt(DnaGraph graph) : base(graph)
            {     
            }
            
            public override void Walk(DnaGraph.Node start)
            {
                PathValue = 0;
                SummaricCost = 0;

                visitedArcs.RemoveRange(0, visitedArcs.Count);
                visitedNodes.RemoveRange(0, visitedNodes.Count);

                visitedNodes.Add(start);
                DnaGraph.Arc nextArc = start.GetNext(visitedNodes);
                if (nextArc == null)
                    return;

                visitedArcs.Add(nextArc);

                SummaricCost += nextArc.Cost;
                if (!(SummaricCost <= _graph.TotalCost))
                {
                    SummaricCost -= nextArc.Cost;
                    return;
                }

                DnaGraph.Node nextNode;
                while (SummaricCost <= _graph.TotalCost)
                {
                    
                    nextNode = _graph.Nodes[nextArc.NodeString];
                    visitedNodes.Add(nextNode);
                    nextArc = nextNode.GetNext(visitedNodes);
                    if (nextArc == null)
                        return;
                    
                    visitedArcs.Add(nextArc);

                    SummaricCost += nextArc.Cost;
                }
                visitedArcs.RemoveAt(visitedArcs.Count - 1);
                visitedNodes.RemoveAt(visitedNodes.Count - 1);
                SummaricCost -= nextArc.Cost;
            }
        }

        protected List<Ant> ants = null;
        protected DnaGraph _graph = null;
        protected List<string> _startingNodes = null;

        public int Ranks { get; set; }
        protected Ant BestSoFar;
        protected int noBetter;

        public AntSystem(int nrAnts, DnaGraph graph, List<string> startingNodes)
        {
            Ranks = 50;
            _graph = graph;
            _startingNodes = startingNodes;

            ants = new List<Ant>();
            for (int i = 0; i < nrAnts; i++)
                ants.Add(new Ant(_graph));
        }

        protected AntSystem() { }

        public delegate void AntProc(Ant ant,DnaGraph.Node start);

        public void AntRun(Ant ant, DnaGraph.Node start)
        {
            ant.Walk(start);
            ant.Eval();
        }

        public void Iterate(DnaGraph.Node start)
        {
            AntProc proc = new AntProc(AntRun);

            List<IAsyncResult> processed = new List<IAsyncResult>();

            foreach (Ant ant in ants)
            {
                processed.Add(proc.BeginInvoke(ant, start, null, null));
            }

            foreach (var result in processed)
            {
                proc.EndInvoke(result);
            }

            ants.Sort(Ant.cmp);
            for (int i = 0; i < Ranks; i++)
            {
                ants[i].LayFeromone();
            }

            if (BestSoFar == null || BestSoFar.PathValue < ants[0].PathValue)
            {
                /*if(BestSoFar != null)
                    System.Console.WriteLine("Old-> " + BestSoFar.PathValue + " New-> " + ants[0].PathValue);*/
                BestSoFar = ants[0].Copy();
                noBetter = 0;                
            }
            else
            {
                BestSoFar.LayFeromone();
                noBetter++;
            }

            _graph.Update();
        }

        public Ant Solve(DnaGraph.Node start)
        {            
            //_graph.Reset();
                        
            Iterate(start);
            
            return BestSoFar;
        }

        virtual public Ant SolveAll(int iterations)
        {
            int max = iterations;
            int curr = 0;
            List<Ant> list = new List<Ant>();
            BestSoFar = null;
            while (iterations >= 0)
            {
                foreach (string str in _startingNodes)
                {
                    
                    DnaGraph.Node start = _graph.Nodes[str];
                    Ant ant = Solve(start);
                    list.Add(ant.Copy());
                    //System.Console.WriteLine("NB>> " + noBetter);
                    if (noBetter > _graph.Threshold)
                    {
                        //System.Console.WriteLine("Bazinga!");
                        list.Sort(Ant.cmp);
                        return list[0];
                    }
                    curr++;
                    if(!Program.batch)
                        try
                        {
                            Console.CursorLeft = 0;
                            Console.Write((curr * 100) / max + "%");
                            Console.CursorLeft = 0;
                        }
                        catch (Exception) { }
                    if (--iterations < 0)
                        break;
                }
                
            }
            list.Sort(Ant.cmp);
            return list[0];
        }

        public static string AntToDNA(Ant ant)
        {
            string result = "";
            result += ant.visitedNodes[0].value;

            foreach (DnaGraph.Arc arc in ant.visitedArcs)
            {
                //Console.WriteLine(">>>" + arc.NodeString);
                string nodeStr = arc.NodeString.Substring(arc.NodeString.Length - arc.Cost);
                result += nodeStr;
            }
            return result;
        }
    }

    class NegAntSystem : AntSystem
    {
        public NegAntSystem(int nrAnts, DnaGraph graph, List<string> startingNodes)
        {
            Ranks = 50;
            _graph = graph;
            _startingNodes = startingNodes;

            ants = new List<Ant>();
            for (int i = 0; i < nrAnts; i++)
                ants.Add(new NegativeAnt(_graph));
        }

        public override Ant SolveAll(int iterations)
        {
            int max = iterations;
            int curr = 0;
            List<Ant> list = new List<Ant>();
            BestSoFar = null;
            do
            {
                foreach (string str in _startingNodes)
                {

                    DnaGraph.Node start = _graph.Nodes[str];
                    Ant ant = Solve(start);
                    list.Add(ant.Copy());
                    //System.Console.WriteLine("NB>> " + noBetter);
                    if (noBetter > _graph.Threshold)
                    {
                        //System.Console.WriteLine("Bazinga!");
                        list.Sort(Ant.cmp);
                        return list[0];
                    }
                    curr++;
                    if (!Program.batch)
                        try
                        {
                            Console.CursorLeft = 0;
                            Console.Write((curr * 100) / max + "%");
                            Console.CursorLeft = 0;
                        }
                        catch (Exception) { }
                    if (--iterations < 0)
                        break;
                }
            }
            while (BestSoFar.SummaricCost > _graph.TotalCost);

            list.Sort(Ant.cmp);
            return list[0];
        }
    }
}
